#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007

struct my_struct
{
    int x;
    int y;
    int state;

    my_struct(int x, int y, int st): x(x), y(y), state(st)
    {
    }
};

class Solution
{
public:
    int shortestPathAllKeys(std::vector<std::string>& grid)
    {
        std::array<int, 5> move = {-1, 0, 1, 0, -1};
        int n = grid.size();
        int m = grid[0].size();
        std::deque<my_struct> q;
        std::vector<std::vector<std::vector<bool>>> visited(
          n, std::vector<std::vector<bool>>(m, std::vector<bool>(1 << 6, false)));

        int key = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f')
                {
                    key |= 1 << (grid[i][j] - 'a');
                }
                if (grid[i][j] == '@')
                {
                    q.emplace_back(i, j, 0);
                    visited[i][j][0]=true;
                }
            }
        }
      
        int level = 0;
        while (!q.empty())
        {
            int size = q.size();
            level++;
            while (size--)
            {
                my_struct temp = q.front();
                q.pop_front();
                for (int i = 0; i < 4; i++)
                {
                    int x = temp.x + move[i];
                    int y = temp.y + move[i + 1];
                    int s = temp.state;
                    if (x < 0 || y < 0 || x > n - 1 || y > m - 1)
                    {
                        continue;
                    }
                    if (visited[x][y][s] || grid[x][y] == '#')
                        continue;
                    if (grid[x][y] >= 'A' && grid[x][y] <= 'F' && (s & 1 << (grid[x][y] - 'A')) == 0)
                    {
                        continue;
                    }
                  
                    if (grid[x][y] >= 'a' && grid[x][y] <= 'f')
                    {
                        s |= 1 << (grid[x][y] - 'a');
                    }
                    if (s == key)
                    {
                        return level;
                    }
                    q.emplace_back(x, y, s);
                    visited[x][y][s] = true;
                }
            }
     
        }
        return -1;
    }
};
